package class28;

import com.sun.org.apache.bcel.internal.generic.NEW;

/**
 * @author zhangchaoliang
 * create 2022
 */
public class TrappingRainWater {

    public static int water1(int[] arr){
        if (arr==null || arr.length<2){
            return 0;
        }
        int  N = arr.length;
        int water = 0;
        for (int i = 1;i<N-1;i++){
            int leftMax = Integer.MIN_VALUE;
            for (int j = 0;j<i;j++){
                leftMax = Math.max(leftMax,arr[j]);
            }
            int rightMax = Integer.MIN_VALUE;
            for (int j = i+1;j<N;j++){
                rightMax = Math.max(rightMax,arr[j]);
            }
            water += Math.max(Math.min(leftMax,rightMax)-arr[i],0);
        }
        return water;
    }

    public static int water2(int[] arr){
        if (arr == null || arr.length < 2){
            return 0;
        }
        int N = arr.length;
        int[] leftMax = new int[N];
        leftMax[0] = arr[0];
        for (int i =1;i<N;i++){
            leftMax[i] = Math.max(leftMax[i-1],arr[i]);
        }
        int[] rightMax = new int[N];
        rightMax[N-1] = arr[N-1];
        for (int i = N-2;i>=0;i--){
            rightMax[i] = Math.max(rightMax[i+1],arr[i]);
        }
        int water = 0;
        for (int i = 1;i<N-1;i++){
            water += Math.max(Math.min(leftMax[i-1],rightMax[i+1])-arr[i],0);
        }
        return water;
    }

    public static int water3(int[] arr){
        if (arr == null ||arr.length<2){
            return 0;
        }
        int N = arr.length;
        int[] rightMaxs = new int[N];
        rightMaxs[N-1] = arr[N-1];
        for (int i =N-2;i>=0;i--){
            rightMaxs[i] = Math.max(rightMaxs[i+1],arr[i]);
        }
        int water = 0;
        int leftMax = arr[0];
        for (int i = 1;i<N-1;i++){
            water += Math.max(Math.min(leftMax,rightMaxs[i+1])-arr[i],0);
            leftMax = Math.max(leftMax,arr[i]);
        }
        return water;
    }

    public static int water4(int[] arr){
        if (arr == null ||arr.length<2){
            return 0;
        }
        int N = arr.length;
        int L = 1;
        int leftMax = arr[0];
        int R = N-2;
        int rightMax = arr[N-1];
        int water = 0;
        while (L<=R){
            if (leftMax <= rightMax){
                water += Math.max(0,leftMax-arr[L]);
                leftMax = Math.max(leftMax,arr[L++]);
            }else {
                water += Math.max(0,rightMax-arr[R]);
                rightMax = Math.max(rightMax,arr[R--]);
            }
        }
        return water;
    }
}
